/*
	Program	:		Solution to Eight puzzle with A* algorithm using heuristics
	Author	:		Sreejith Sreekantan
	Date	:		March, 2013
	TODO	:
					Avoid duplicates in priority_queue
					Implement hasSolution() for Solver
*/

#include <iostream>
#include <boost/foreach.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/shared_ptr.hpp>
#include <vector>
#include <queue>
#include <boost/numeric/ublas/matrix.hpp>
#include <cmath>
#include <exception>
#include <syslog.h>

#define BLANK_SPACE 0
#define INVALID -999

using namespace std;
using namespace boost;

class Board
{
	friend class Solver;
private:
	boost::numeric::ublas::matrix< int > _board;
	boost::numeric::ublas::matrix< int > goalBoard;
	int _num_of_moves_from_start;
	
public:
	Board() {
		_num_of_moves_from_start = 0;
	}
	
	Board( const Board & board ) {
		_board = board._board;
		initGoalBoard( board._board.size1() );
		_num_of_moves_from_start = board._num_of_moves_from_start;
	}
	
	void operator=(const Board & board ) {
		_board = board._board;
		initGoalBoard( board._board.size1() );
		_num_of_moves_from_start = board._num_of_moves_from_start;
	}
	
	bool operator==(const Board & board ) {
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				if( _board( i, j ) != board._board( i, j )) {
					return false;
				}	
			}
		}
		return true;
	}
		
	void readMatrix() {
		int	size_of_matrix=3;
		cout << "Size of Matrix(Input n to create n-by-n matrix): ";
		cin >> size_of_matrix;
		initGoalBoard( size_of_matrix );
		_board.resize( size_of_matrix, size_of_matrix, false );
		int temp_inp;
		_board.resize(3,3,false);
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				cin >> temp_inp;
				_board( i, j ) = temp_inp;	
			}
		}
	}
	
	void initGoalBoard(int size) {
		goalBoard.resize( size, size, false );
		int temp = 1;
		for( int i = 0; i < size; i++ ) {
			for( int j = 0; j < size; j++ ) {
				goalBoard( i, j ) = temp++;
			}
		}
		goalBoard( size-1, size-1 ) = BLANK_SPACE;
	}
	
	int manhatten() const
	{
		int manhatten_dist = 0;
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				if( _board( i, j ) != goalBoard( i, j ) ) {
					manhatten_dist += abs(i - ( i / (int)_board.size1() ) );
					manhatten_dist += abs(j - ( j % (int)_board.size1() ) );
				}
			}
		}
		return ( manhatten_dist + _num_of_moves_from_start );
	}
	
	int hamming() const
	{
		int hamming_dist = 0;
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				if( _board( i, j ) != goalBoard( i, j ) ) {
					hamming_dist ++;
				}
			}
		}
		
		hamming_dist += _num_of_moves_from_start;
		
		return hamming_dist;
	}
	
	void swap( pair< int, int > a, pair< int, int > b ) {
		int temp = _board( a.first, a.second );
		_board( a.first, a.second ) = _board( b.first, b.second );
		_board( b.first, b.second ) = temp;
		_num_of_moves_from_start++;
	}
	
	void neighbours( shared_ptr< std::vector<Board> > vector_neighbours ) const{
		Board temp_board;
		int blank_x=INVALID, blank_y;
		// blank_x == INVALID is used to stop loop after blank space is found
		for( int i = 0; i < _board.size1() && blank_x == INVALID; i++) {
			for( int j = 0; j < _board.size1() && blank_x == INVALID; j++ ) {
				if( _board( i, j ) == BLANK_SPACE ) {
					blank_x = i;
					blank_y = j;
				}
			}
		}
		for( int i = -1; i <= 1; i++ ) {
			for( int j = -1; j <= 1; j++ ) {
				if
				( 
						i == 0 && j == 0 								// same position 
					||	i == j
					||	blank_x + i < 0 || blank_x + i >= _board.size1()	// x-coord goes out of board
					||	blank_y + j < 0 || blank_y + j >= _board.size1()	// y-coord goes out of board
				) 
				{
					continue;
				}
				temp_board = *this;
				temp_board.swap( make_pair( blank_x, blank_y ), make_pair( blank_x + i, blank_y + j ) );
				
				vector_neighbours->push_back( temp_board );
				
			}
		}
	}
	
	bool isGoal() const {
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				if( _board( i, j ) != goalBoard( i, j )) {
					return false;
				}	
			}
		}
		return true;
	}
	
	string toString() const
	{
		string output;
		for( int i = 0; i < _board.size1(); i++ ) {
			for( int j = 0; j < _board.size1(); j++ ) {
				output += ( lexical_cast< string >( _board( i, j ) ) );
				output += " ";
			}
			output += "\n";
		}
		return output;
	}
};

ostream & operator<<( ostream & out, const Board & board )
{
	out << "\n" << board.toString();
	return out;
}

class CompareBoardHamming {
public:
	bool operator()( const Board a, const Board b ) {
		return a.hamming() > b.hamming();
	}
};

class Solver 
{
	Board initial_board;

public:
	Solver( const Board &board ) {
		initial_board = board ;
	}
	
	void solution( shared_ptr< std::vector<Board> > solution) {
		std::priority_queue< Board, std::vector<Board>, CompareBoardHamming > p_q;
		p_q.push( initial_board );
		Board temp_board;
		shared_ptr< std::vector<Board> > vector_neighbours( new std::vector<Board>() );
		while ( !p_q.empty() ) {
			Board p_q_top = p_q.top();
			p_q.pop();
			solution->push_back( p_q_top );
			if( p_q_top.isGoal() ) 
			{
				break;
			}
			else 
			{
				vector_neighbours->resize(0);
				p_q_top.neighbours( vector_neighbours );
				for(std::vector<Board>::iterator neigh = vector_neighbours->begin(); neigh != vector_neighbours->end(); neigh++ ) {
					temp_board = *neigh;
					
					p_q.push( temp_board );
					
				}
			}
		}
	}
};

class B { public: int a; };
class comp { public: bool operator()(const B& a, const B& b) { return a.a < b.a; } };

int main( int argc, char * argv[] ) 
{
	int size_of_matrix=3;
	Board b;

	//automated for now
	b.readMatrix();
		
	cout << "path to goal:" << endl;
	Solver solver( b );
	shared_ptr< std::vector<Board> > vector_solution( new std::vector<Board>() );
	solver.solution( vector_solution );
	
	BOOST_FOREACH( Board neigh, *vector_solution ) {
		cout << neigh << endl;
	}
	cout << "exit main" << endl;
}